package leetcode;

/**
 * 动态规划：最后一块石头的重量
 */
public class Solution45 {
    class Solution {
        public int lastStoneWeightII(int[] stones) {
            if(stones == null || stones.length == 0){
                return 0;
            }
            int sum = 0;
            for(int sums : stones){
                sum = sum + sums;
            }
            int target = sum / 2;
            int[] dp = new int[target + 1];
            for(int i= 0;i < stones.length;i++){
                for(int j = target ; j >= stones[i];j--){
                    dp[j] = Math.max(dp[j],dp[j - stones[i]] + stones[i]);
                }
            }
            return sum - 2*dp[target];
        }
    }
}
